package kyssion.leetcode.num201_250;

import kyssion.leetcode.util.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class code236_二叉树的最近公共祖先 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.create(
                new int[]{
                        3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4
                }
        );
    }

    Deque<TreeNode> ps;
    Deque<TreeNode> qs;
    boolean findp;
    boolean findq;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ps = new LinkedList<>();
        qs = new LinkedList<>();
        findp = false;
        findq = false;
        ans(root, p, q);
        TreeNode parent = null;
        while (!ps.isEmpty() && !qs.isEmpty()) {
            if (ps.getFirst() == qs.getFirst()) {
                parent = ps.getFirst();
                ps.removeFirst();
                qs.removeFirst();
            } else {
                break;
            }
        }
        return parent;
    }



    private void ans(TreeNode root, TreeNode p, TreeNode q) {
        if (findp && findq || root == null) {
            return;
        }
        if (!findp) {
            ps.addLast(root);
        }
        if (!findq) {
            qs.addLast(root);
        }
        if (root == p) {
            findp = true;
        }
        if (root == q) {
            findq = true;
        }
        ans(root.left, p, q);
        ans(root.right, p, q);
        if (!findp) {
            ps.removeLast();
        }
        if (!findq) {
            qs.removeLast();
        }
    }

    TreeNode parent;

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        parent = null;
        abs(root, p, q);
        return parent;
    }

    private TreeNode abs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || parent != null) {
            return null;
        }

        if (root == p || root == q) {
            TreeNode left = abs(root.left, p, q);
            TreeNode right = abs(root.right, p, q);
            if (left != null || right != null) {
                parent = root;
                return null;
            } else {
                return root == p ? p : q;
            }
        } else {
            TreeNode left = abs(root.left, p, q);
            TreeNode right = abs(root.right, p, q);
            if (left != null && right != null) {
                parent = root;
                return null;
            }
            return left == null ? right : left;
        }
    }


    /**
     * 玄学，不过是一直中思想，使用数字加速
     */
    TreeNode result;

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        result = null;
        count(root, p, q);
        return result;

    }

    private int count(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }
        int r = 0;
        if (root.val == p.val || root.val == q.val) {
            r++;
        }
        r += count(root.left, p, q);
        r += count(root.right, p, q);
        if (r == 2) {
            result = root;
            return 0;
        }
        return r;
    }
}
